🎒 Alice's Fractional Knapsack Problem

Visualize the Greedy Algorithm to maximize value in a limited-capacity backpack.

💰 Alice's Valuable Haul

🎯 The Challenge:

Alice must select items to maximize the total value carried in a backpack with a **limited weight capacity (W)**. Since it's fractional knapsack, she can take parts of items.

📋 Key Requirements:

  • **4 Fixed Items** (Value $v$ and Weight $w$ for each).
  • Maximize total value $\sum v_i \cdot x_i$ subject to $\sum w_i \cdot x_i \leq W$, where $0 \leq x_i \leq 1$.
  • The solution uses the **Greedy Approach**.

Problem Specifications (Example Input)

Input is 4 lines of (Value Weight), followed by the Capacity W.

300 6
150 3
120 3
100 2
10  <- Capacity W

Expected Output for Example

Values: 300 150 120 100 
Weights: 6 3 3 2 
Total weight in bag: 10.00
Max value for 10 weight is 500.00

🧠 The Greedy Strategy: Value Density

Core Steps to Maximize Value

  1. **Calculate Ratios:** For every item $i$, calculate the **Value-to-Weight Ratio** (or **Value Density**): $R_i = v_i / w_i$.
  2. **Sort:** Sort all items in **descending order** based on $R_i$. This is the crucial greedy step.
  3. **Fill Knapsack:** Iterate through the sorted list and try to fit each item into the remaining capacity.
    • If the item fits entirely, take it and update the remaining capacity.
    • If only a fraction fits, take that fraction, and the capacity becomes zero (knapsack is full).

Time Complexity

O(N log N)

Dominated by the initial $O(N \log N)$ sorting step.

Why Greedy Works

Fractional

Because we can take fractions, picking the highest $v/w$ ratio guarantees maximum value per unit of weight taken at every step, leading to the overall optimum.

🔍 Step-by-Step Knapsack Filling Demo

Ready. Click Start to initialize the knapsack calculation.

Items Sorted by Value Density ($v/w$)

Capacity Remaining: 10.00

Total Value Achieved: 0.00

Progress tracker

1. Parse input and calculate Value/Weight Ratios ($v/w$).
2. **Sort** items by $v/w$ ratio in descending order.
3. Iterate through items: check if item fits fully.
4. If capacity remains, take a fraction, update total weight/value, and finish.
5. Final calculation and output.

🎮 Practice Knapsack Filling

Enter items/capacity and press Solve Knapsack

📊 Analysis & Key Takeaways

Greedy Optimality

Yes

The fractional nature allows the greedy approach (based on $v/w$) to guarantee the global optimum.

0/1 Knapsack

No

The **0/1 Knapsack** (no fractions allowed) is **NOT** solvable by this greedy method; it requires Dynamic Programming.

The Difference Maker: Fractions

The ability to take a fraction of an item means that if we are forced to stop, we can ensure that the last unit of weight we take provides the maximum possible value (by picking from the highest $v/w$ item). This property is what makes the simple greedy choice work.